//
// Created by Lenovo on 2024/1/31.
//
#include<bits/stdc++.h>
using namespace std;
class Solution {
public:

    vector<vector<string>> result;      //返回结果集
    vector<string> path;                // 放已经回文的子串

    //判断是否为回文串
    bool judge(string str,int l,int r){
        for(int i=l,j=r;i<j;i++,j--){
            if(str[i]!=str[j])
                return false;
        }
        return true;
    }

    void dfs(string &s,int startIndex){
        if(startIndex>=s.size()){
            result.push_back(path);
        }
        for(int i=startIndex;i<s.size();i++){
            if(judge(s,startIndex,i)){                              //如果是回文串
                string str=s.substr(startIndex,i-startIndex+1);      //分割子串
                path.push_back(str);                                         //存入当前子串集合中
                dfs(s,i+1);                                      //继续深搜
                path.pop_back();                                              //回溯
            }
        }
    }

    vector<vector<string>> partition(string s) {
        dfs(s,0);
        return result;
    }
};